Recursion in Scala

Recursion is a method which breaks the problem into smaller sub problems and calls itself for each of the problems.For example, a function ‘A’ calls function ‘B’, which calls the function ‘C’.That is, it simply means function calling itself. We can use recursion instead of loops. Recursion avoids mutable state associated with loops. Recursion is quite common in functional programming and provides a natural way to describe many Algorithms. Recursion is considered as to be important in functional programming. Scala supports Recursion very well.

Find the factorial of numbers

object demo
{
  def fact(n:Int): Int=
  {
    if(n == 1) 1
    else n * fact(n - 1)
  }
def main(args:Array[String])
  {
    println(fact(8))
  }
}

Find the sum of numbers

object demo
{
  def sum(n:Int): Int=
  {
    if(n == 1) 1
    else n + sum(n - 1)
  }
def main(args:Array[String])
  {
    println(sum(5))
  }
}
In the above example, the base case for n < = 1 is defined and a larger value of a number can be solved by converting to a smaller one till the base case is reached.  
Why StackOverflow error occurs in recursion? 
If the base case is not reached or not defined or if the recursion depth is too deep, then the StackOverflow problem may arise. Let us take an example to understand this.


If factorial(25) is called, the value of n will be 25, 24, 23, 22, and so on but the number will never reach 500. So, the base case is not reached. If the memory is exhausted by these functions on the stack, it will cause a StackOverflow error. 
Tail Recursion
“Functions which call themselves as their last action are called tail-recursive.The Scala compiler detects tail recursion and replaces it with a jump back to the beginning of the function, after updating the function parameters with the new values … as long as the last thing you do is calling yourself, it’s automatically tail-recursive (i.e., optimized).”
def improvedFactorial(n: Int): BigInt = {
    @tailrec
    def factHelper(x: Int, accumulator: BigInt): BigInt =
      if (x <= 1) accumulator
      else factHelper(x-1, x * accumulator)
    factHelper(n, 1)
  }
  println(improvedFactorial(5))

Let’s break down each step of the recursion when we call factHelper.
First we call it with factHelper(5,1)
This goes into the else block and calls factHelper(4, 4 * 1).
Then into the else block again with factHelper(3, 3 * 4 * 1).
Then again with factHelper(2, 2 * 3 * 4 * 1).
So we can see the accumlator building up here. You can try calling this function to get the factorial of a large number (e.g. 6000) and it will work.
But why does this work without causing the stack overflow error like the previous function implementation? 
Because we wrote factHelper as the last expression of the code path. This allows Scala to preserve the same stack frame through the recursive calls, instead of using additional frames for each call.
This is called Tail Recursion . The key to making a function tail recursive is to make the last expression in the function recursive.
To force the compiler to check for a tail recursive function, you can add the @tailrec annotation. If your function isn’t tail recursive, the compiler will throw an error:

    @tailrec
    def factHelper(x: Int, accumulator: BigInt): BigInt =
    // ...
When you need to loop in Scala, you should look to use Tail Recursion.
The trick is to use variables like the accumulator in the above function to store the intermediate results, rather than calling the main function recursively. You need as many accumulators as you have recursive calls, and sometimes more.
This technique can take some time to grasp, but becomes easier with experience and practice.

Scala supports tail recursive functions by performing tail call optimization. It also has a special annotation, @tailrec, to ensure that the method can be executed in a tail recursive manner, otherwise the compiler produces error.